package com.dragon.datastructure.tree.redblacktree;

/**
 * 红黑树
 * <p>
 * 红黑树是等价于23树的
 * 红黑树的性质:
 * 1.红黑树也是一颗二分搜素树
 * 2.红黑树中的节点要么是黑色的要么是红色的
 * 3.红黑树中的根节点为黑色的
 * 4.红黑树的叶子节点(为null的节点)是黑色的，如果一颗红黑树它是一颗空树，则能保持节点是黑色的，同时叶子节点也是黑色的
 * 5.红黑树中红色节点的直接子节点一定是黑色的,因为红色节点一定是向做倾斜的，它代表了与自己的父类的融合(等价于23树中的3节点)，所以红色节点的子节点一定是黑色的
 * 6.红黑树中对于每一个节点到叶子节点(为null的节点)走过的黑色节点的数量是一样的，因为红黑树是一颗保持绝对"黑平衡"的二叉树，可以等价于23树(绝对平衡树，代表对于每一个节点，左右子树的高度相等)，所以经过的黑色节点数量是相同的
 * <p>
 * 红黑树的时间复杂度分析:
 * <p>
 * 红黑树的高度最大为2 * log(N),因为有可能对于每一个节点都是3节点
 * 插入: log(N)
 * 查询: log(N)
 * 修改: log(N)
 * 删除: log(N)
 * <p>
 * 红黑树与AVl树的性能比较:
 * AVl树的高度最差也为log(N),所以相较于红黑树来说，AVl树的查询性能是高于红黑树的，
 * 但是AVl树的添加，删除，需要维护自平衡，维护节点的高度，以及计算平衡因子，所以红黑树的添加，删除的性能是高于AVL树的
 * <p>
 * 所以，从综合性能来考虑的话，红黑树是优于AVL树的
 *
 * @author dragon
 * @since 2020/1/4
 */
public class RedBlackTree<E extends Comparable<E>> {

    private static final boolean RED = true;

    private static final boolean BLANK = false;

    private int size;

    private Node root;

    private class Node {

        E item;

        boolean color;

        Node left;

        Node right;

        // 对于每一个新创建的节点默认都为红色的，这是因为每一个新添加的节点都需要与其他的节点先进行融合，我们用红色表示23树中的融合
        public Node(E item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
            color = true;
        }

        // 对于每一个新创建的节点默认都为红色的，这是因为每一个新添加的节点都需要与其他的节点先进行融合，我们用红色表示23树中的融合
        public Node() {
            color = true;
        }

    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        root = addRec(root, e);
        // 红黑树中的性质，对于每一个节点都必须为黑色，而融合上来的root根节点有可能为红色的，所以我们这里设置根节点的颜色为黑色的
        root.color = BLANK;
    }

    private Node addRec(Node node, E e) {
        // 这是一个递归到底的情况，说明这个位置是空的，可以添加节点
        if (node == null) {
            size++;
            return new Node(e, null, null);
        }
        // 如果我想要添加的元素比node小，则我肯定往node的左子树中去找位置
        if (node.item.compareTo(e) > 0) {
            node.left = addRec(node.left, e);
        }
        // 如果我想要添加的元素比node大，则我肯定往node的右子树中去找位置
        else if (node.item.compareTo(e) < 0) {
            node.right = addRec(node.right, e);
        }
        // 如果相同，则直接修改
        else {
            node.item = e;
        }

        // 如果该节点的右子节点为红色，但是该节点的左子节点不为红色，就是为黑色(也有可能就是为null)
        if (isRed(node.right) && !isRed(node.left)) {
            node = leftRotate(node);
        }
        // 如果该节点的左子节点为红色，同时该节点的左子节点的左子节点也是红色的，这个时候需要右旋转
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rightRotate(node);
        }
        // 如果该节点的左右子节点都为红色的，这个时候要进行颜色的反转
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }

        return node;
    }

    /**
     * 判断红黑树中是否包含指定的元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        if (e == null) {
            return false;
        }

        return containsRec(root, e);
    }

    private boolean containsRec(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (node.item.compareTo(e) > 0) {
            return containsRec(node.left, e);
        } else if (node.item.compareTo(e) < 0) {
            return containsRec(node.right, e);
        } else {
            return true;
        }
    }

    /**
     * 判断节点是否为红色，为null的节点为黑色，这是红黑树的定义
     *
     * @param node
     * @return
     */
    private boolean isRed(Node node) {
        if (node == null) {
            return false;
        }

        return node.color;
    }

    /**
     * 左旋转
     *
     * @param y
     * @return
     */
    private Node leftRotate(Node y) {
        /*
         * 往红黑树中添加元素有两种大类情况，第一种是往一个2节点中添加元素，第二种往一个3节点中添加元素
         *
         *
         * 第一种往一个2节点中添加元素，如果是添加到这个2节点的左边，这样就很完美，因为新添加进来的元素是红色，代表在23树中他们是融合在一起的，说明他们是一个三节点
         * 如果添加元素，添加到这个2节点的右边，这样，就需要左旋转，因为我们自己定义了，红色节点都往左边倾斜，代表红色节点与它的父亲一起是一个三节点
         */
        // 左旋转
        Node x = y.right;
        y.right = x.left;
        x.left = y;

        // 上色
        x.color = y.color;
        y.color = RED;

        return x;
    }

    /**
     * 右旋转
     *
     * @param y
     * @return
     */
    private Node rightRotate(Node y) {
        /*
         * 第二种就是往一个3节点中添加元素，如果添加的元素在3节点的左边，这个是否组成一个临时的4节点，
         * 这个是否需要右旋转
         */
        // 右旋转
        Node x = y.left;
        y.left = x.right;
        x.right = y;

        // 上色
        x.color = y.color;
        y.color = RED;

        return x;
    }

    /**
     * 颜色反转
     *
     * @param node
     */
    private void flipColors(Node node) {
        /*
         * 第二中就是往一个3节点中添加元素，如果添加的元素在3节点的右边，就是说比3节点中的2个元素都大，这个是否就是一个临时的4节点，
         * 这个时候，就要变形，就是说这个3个并列的节点，需要以中间节点为根，两边节点为叶子，构建一个二叉树，同时颜色还要进行反转
         */
        node.color = RED;
        node.left.color = BLANK;
        node.right.color = BLANK;
    }


}
